Preprint No. A-01-13

Ehrhard Behrends, Bernd Schmidt

Can one determine a graph by counting walks?

Abstract: Let $G$ be a rooted graph with root $x_{0}$ and denote, for any positive integer $n$, by $a_{n}$ the number of walks of length $n$ which start at $x_{0}$. Is it possible to identify $G$ up to isomorphism from the sequence $(a_{n})$? This problem can be thought of as a disrete variant of Kac' famous ``Can you hear the shape of a drum?''. In the present paper it is analysed in detail for a certain rather simple class of rooted trees.

Keywords: tree, identification problem, random walk, drum

Mathematics Subject Classification (MSC2000): Primary 05C05. Secondary 05C60, 60J10.

Language: ENG

Available: Pr-A-01-13.ps

Contact: Ehrhard Behrends, Freie Universität Berlin, Fachbereich Mathematik und Informatik, Arnimallee 2-6, D-14195 Berlin, Germany (behrends@math.fu-berlin.de)

[Home Page] - [Up] - [Search] - [Help] - Created: 20010703 -